1. Field
The present invention relates to modeling and testing digital designs of state machines, and more specifically, to systems, methods and computer products for the identification of dependent state variables to aid in logic design and verification.
2. Description of Related Art
A system such as an electrical circuit including state holding elements may be modeled using state equations and state variables that describe the behavior and state of the system. A complete set of state variables, coupled with logic that de-fines the transitions between states, for a system typically contains enough information about the system's history to enable computation of the system's future behavior. Simplifying the model to reduce the number of state variables, or simplifying the logic that defines state transitions, lessens the computational cost of analyzing the model for example, to verify that it conforms to a given specification.
Dependent state element identification refers to the process of identifying those state variables in a design (e.g. latches or registers) that can be expressed as combinational (Boolean) functions of other state variables. A special case of dependent state variables are redundant state variables, in which two registers evaluate to the same value at all points in time. For example, one register may be expressible as a function of other registries, e.g., register1 may be equal to the AND of register2 and register3 for all points in time. In such a situation, the register1 state variable is said to be redundant in view of register2 and register3. Redundancy removal—the process of merging two gates that always evaluate to identical values in all “reachable states” of a design—is a very powerful technique to enhance verification.
The computations needed to verify a system design tend to become very expensive as the model being analyzed increases in complexity. Verification paradigms typically suffer exponential runtime with respect to the number of state and logic elements of the design. By identifying behaviorally equivalent state and logic elements within a design, the size of the design may be reduced by eliminating those redundant elements for a particular application.
What is needed is an efficient way to optimally identify and leverage redundant logic elements to streamline the verification process. This disclosure introduces improved mechanisms for identifying redundant logic gates in general verification frameworks.